package com.zhanghp.class01;

import static com.zhanghp.class01.sort.utils.SortUtils.printArr;
import static com.zhanghp.utils.CommonUtils.printDivingLine;
import static com.zhanghp.utils.CommonUtils.rand;

/**
 * 前缀和数组，求数组中指定[L,R]的和
 *
 * @author zhanghp
 * @date 2023-07-29 21:15
 */
public class Code02_PreSum {
    public static void main(String[] args) {
        int l = 3;
        int r = 5;
        int[] arr = rand(20, 10);
        printArr(arr);
        System.out.printf("%s%n", new RangeSum1(arr).rangeSum(l, r));
        printDivingLine();
        System.out.printf("%s%n", new RangeSum2(arr).rangeSum(l, r));
    }

    /**
     * 前缀和实现一：指定左右进行相加
     */
    public static class RangeSum1 {
        int[] arr;

        public RangeSum1(int[] arr) {
            this.arr = arr;
        }

        public int rangeSum(int l, int r) {
            int length = arr.length;
            int sum = 0;
            if ((l - r) > 0 || l >= length || r >= length) {
                return 0;
            }
            for (int i = l; i <= r; i++) {
                sum += arr[i];
            }
            return sum;
        }
    }

    /**
     * 前缀和实现二：提前实现前缀和数组，指定左右后直接相减
     */
    public static class RangeSum2 {
        int[] preSum;

        public RangeSum2(int[] arr) {
            int length = arr.length;
            if (arr == null || length == 0) {
                throw new RuntimeException("数组长度为0");
            }
            preSum = new int[length];
            preSum[0] = arr[0];
            for (int i = 1; i < length; i++) {
                preSum[i] = preSum[i - 1] + arr[i];
            }
        }

        public int rangeSum(int l, int r) {
            int length = preSum.length;
            if ((l - r) > 0 || l >= length || r >= length) {
                return 0;
            }
            printArr(preSum);
            return preSum[r] - preSum[l - 1];
        }
    }
}
